﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QueuesAndStacks.NumIslands
{
    class MainProject
    {
        /// <summary>
        /// 思路：循环每个数值，然后去查找所有的，要是断开了 到于数量+1
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            char[][] nums = new char[][] {
                 new char[]{'1','1','1','1','1','0','1','1','1','1'},
                 new char[]{'1','0','1','0','1','1','1','1','1','1'},
                 new char[]{'0','1','1','1','0','1','1','1','1','1'},
                 new char[]{'1','1','0','1','1','0','0','0','0','1'},
                 new char[]{'1','0','1','0','1','0','0','1','0','1'},
                 new char[]{'1','0','0','1','1','1','0','1','0','0'},
                 new char[]{'0','0','1','0','0','1','1','1','1','0'},
                 new char[]{'1','0','1','1','1','0','0','1','1','1'},
                 new char[]{'1','1','1','1','1','1','1','1','0','1'},
                 new char[]{'1','0','1','1','1','1','1','1','1','0'},
            };
            int res = NumIslands(nums);
            Console.WriteLine(res);
            Console.ReadKey();
        }

        //DFS
        public static int NumIslands(char[][] grid)
        {
            int count = 0;
            for (int i = 0; i < grid.Length; i++)
            {
                for (int j = 0; j < grid[i].Length; j++)
                {
                    if (grid[i][j] == '1')
                    {
                        count++;
                        SetBFS(grid, i, j);
                        //SetDFS(grid, i, j);
                    }
                }
            }
            return count;
        }

        public static void SetBFS(char[][] grid, int i, int j)
        {
            Queue<int> que = new Queue<int>();
            HashSet<int> hash = new HashSet<int>();
            que.Enqueue(i * 1000 + j);
            while (que.Any())
            {
                int size = que.Count;
                //Console.WriteLine("size = "+ size);
                for (int k = 0; k < size; k++)
                {
                    int code = que.Dequeue();
                    int x = code / 1000;
                    int y = code % 1000;
                    Console.WriteLine("size = " + grid[x][y]);
         
                    grid[x][y] = '0';
                    if (x - 1 >= 0 && grid[x - 1][y] == '1') if(hash.Add((x - 1) * 1000 + y)) que.Enqueue((x - 1) * 1000 + y);
                    if (y - 1 >= 0 && grid[x][y - 1] == '1') if (hash.Add((x) * 1000 + (y - 1)))  que.Enqueue((x) * 1000 + (y - 1));
                    if (x + 1 < grid.Length && grid[x + 1][y] == '1') if (hash.Add((x + 1) * 1000 + y)) que.Enqueue((x + 1) * 1000 + y);
                    if (y + 1 < grid[x].Length && grid[x][y + 1] == '1') if (hash.Add(x * 1000 + (y + 1))) que.Enqueue(x * 1000 + (y + 1));
                }
            }
        }

        public static void SetDFS(char[][] grid, int i, int j)
        {
            if (i < 0 || i >= grid.Length || j < 0 || j >= grid[i].Length || grid[i][j] == '0') return;
            grid[i][j] = '0';
            SetDFS(grid, i - 1, j);
            SetDFS(grid, i + 1, j);
            SetDFS(grid, i, j - 1);
            SetDFS(grid, i, j + 1);
        }

        //自己的方法
        public static int NumIslands1(char[][] grid)
        {
            Queue<int[]> que = new Queue<int[]>();
            HashSet<int> hash = new HashSet<int>();
            int count = 0;
            //que.Enqueue(grid[rowIndex][colIndex]);
            for (int i = 0; i < grid.Length; i++)
            {
                for (int j = 0; j < grid[i].Length; j++)
                {
                    if (grid[i][j] == 49)
                    {
                        que.Enqueue(new int[] { grid[i][j], i, j });
                        hash.Add(i * 1000 + j);
                        goto Next;
                    }
                }
            }
            Next:
            //que.Enqueue(grid[rowIndex][colIndex]);
            for (int i = 0; i < grid.Length; i++)
            {
                for (int j = 0; j < grid[i].Length; j++)
                {
                    bool is_49 = false;
                    if (!hash.Contains(i * 1000 + j)) que.Enqueue(new int[] { grid[i][j], i, j });
                    while (que.Count > 0)
                    {
                        int[] cha = que.Dequeue();
                        if (cha[0] == 49)

                        {
                            if (cha[1] == 3 && cha[2] == 1)
                            {

                            }
                            if (cha[1] == 2 && cha[2] == 2)
                            {

                            }
                            if (cha[1] == 2 && cha[2] == 1)
                            {

                            }
                            if (cha[1] == 1 && cha[2] == 2)
                            {

                            }
                            is_49 = true;
                            if (cha[1] - 1 >= 0)
                            {
                                if (grid[cha[1] - 1][cha[2]] == 49)
                                {
                                    if (hash.Add((cha[1] - 1) * 1000 + cha[2]))
                                    {
                                        que.Enqueue(new int[] { grid[cha[1] - 1][cha[2]], cha[1] - 1, cha[2] });
                                    }
                                }
                            }
                            if (cha[2] - 1 >= 0)
                            {
                                if (grid[cha[1]][cha[2] - 1] == 49)
                                {
                                    if (hash.Add((cha[1]) * 1000 + (cha[2] - 1)))
                                    {
                                        que.Enqueue(new int[] { grid[cha[1]][cha[2] - 1], cha[1], cha[2] - 1 });
                                    }
                                }
                            }
                            if (cha[1] + 1 < grid.Length)
                            {
                                if (grid[cha[1] + 1][cha[2]] == 49)
                                {
                                    if (hash.Add((cha[1] + 1) * 1000 + cha[2]))
                                        que.Enqueue(new int[] { grid[cha[1] + 1][cha[2]], cha[1] + 1, cha[2] });
                                }
                            }
                            if (cha[2] + 1 < grid[cha[1]].Length)
                            {
                                if (grid[cha[1]][cha[2] + 1] == 49)
                                {
                                    if (hash.Add(cha[1] * 1000 + cha[2] + 1))
                                        que.Enqueue(new int[] { grid[cha[1]][cha[2] + 1], cha[1], cha[2] + 1 });
                                }
                            }
                        }
                    }
                    if (is_49)
                    {
                        count++;
                    }
                }
            }
            return count;
        }
    }
}
